
#include "gtest/gtest.h"
#include <cassert>
#include <sstream>
#include <cstdlib>

struct Node {
  int key_;
  int value_;
  int level_;
  Node * ptr_[0];

  //level -> 0-based
  static Node * alloc(int level, int key = 0, int value = 0){
    Node * ret = (Node*) std::calloc(1, sizeof(Node) + (level + 1) * sizeof(Node*));
    ret->level_ = level; 
    ret->key_ = key;
    ret->value_ = value;
    return ret;
  }
  static void dealloc(Node* ptr){
    std::free(ptr);
  }

  std::string to_string() const{
    std::ostringstream oss;
    oss 
      << " k:"  << key_
      << " level:"  << level_
      << " &:"  << this
      << " v:"  << value_
      << " nexts:[";
    for( int i = 0; i < level_ + 1; ++i){
      oss << i << "->" << ptr_[i] << " ";
    }
    oss << "]";
    return oss.str();
  }
  //0-based
  int level() const {
    return level_;
  }

  Node * next(int i) {
    assert(i <= level_ && i >= 0);
    return ptr_[i];
  }
  //no check 
  void setNext(int i, Node * nextPtr){
    assert(i <= level_ && i >= 0);
    ptr_[i] = nextPtr;
  }

  void keyValue(int key, int value) {
    key_ = key;
    value_ = value;
  }
  inline const int value()const {
    return value_;
  }
  inline const int key() const {
    return key_;
  }
};


TEST(NodeTest, test){
  Node * head = Node::alloc(6);
  std::cout << head->to_string() << std::endl;
  Node::dealloc(head);
}

class SkipList {
public:
  SkipList()
  : level_(0)
  , header_(Node::alloc(max_level_))
  , tail_(Node::alloc(max_level_))
  , count_(0)
  {
    for(int i = 0 ; i < header_->level() + 1; i++){
      header_->setNext(i, tail_);
    }

    std::srand(time(0));
  }


  ~SkipList(){
    destroy();
    Node::dealloc(tail_);
    Node::dealloc(header_);
  }


  std::pair<bool, int> get(const int key) {
    Node * p = header_;
    for( int i = level_; i >= 0; i --){
      while( p->next(i) != tail_ && p->next(i)->key_ < key) {
        p = p->next(i);
      }

      if(p->next(i)->key_ == key){
        return std::make_pair(true, p->next(i)->value_);
      }
    }
    return std::make_pair(false, 0);
  }

  
  std::pair<bool, int> insert(const int key, const int value) {
    //find the pre_ptrs
    Node * prevs[SkipList::max_level_+1] = {0};
    
    Node * p = header_;
    for(int i = level_; i>= 0 ; i--){
      while( p->next(i) != tail_ &&  p->next(i)->key_ < key)
        p = p->next(i);
      prevs[i] = p;
    }

    Node * cur = p->next(0);
    if(cur != tail_ && cur->key_ == key){ // find the key
      int old = cur->value_;
      cur->keyValue(key, value);
      return std::make_pair(true, old);
    }

    int newLevel = randomLevel(); 
    std::cout << "random newLevel: " << newLevel 
      << " old level_ : " << level_
      << std::endl;

    if(level_ < newLevel){

      for(int i = level_ + 1; i <= newLevel; ++i){
        prevs[i] = header_;
      }

      level_ = newLevel;
    }

    cur = Node::alloc(newLevel, key, value);

    for(int i = newLevel; i>= 0; i--){
      cur->setNext(i, prevs[i]->next(i));
      prevs[i]->setNext(i,  cur);
    }

    count_ ++;
    return std::make_pair(true, 0); 
  }

  int randomLevel() const{ //TODO: to be noted
#if 0
    static int a[] = {0, 0, 1};
    static int count = 0;
    return a[count++];
#else
    int level = 0;
    while(std::rand() %2) {
      ++level;
    }
    return (level > max_level_) ? (max_level_) : level;
#endif
  }


  void print(const std::string & remind = "") {
    std::cout <<  "Skiplist : " << remind  << ":" << std::endl;

    std::cout 
      << " count: " << count_ 
      << " level: " << level_
      << std::endl;

    std::cout << " header_: " << header_->to_string() << std::endl;

    for(int i = 0; i <= level_; ++i){
      std::cout << "[level:" << i  << std::endl;
      Node * p = header_;
      while( p->next(i) != tail_) {
        std::cout << "  --" << p->next(i)->to_string() << std::endl;
        p = p -> next(i);
      }
      std::cout << "level: " << i << "]" << std::endl << std::endl;
    }
    std::cout << " tail_  : "<< tail_  ->to_string() << std::endl;
    std::cout << std::endl;
  }

  
  std::pair<bool, int> remove(int key) {
    Node * pc = header_;
    Node * prevs[max_level_ + 1] = {0};
    for(int i = level_; i >= 0; --i){
      while(pc->next(i) != tail_ && pc->next(i)->key_ < key) 
        pc = pc->next(i);
      prevs[i] = pc;
    }
    
    Node * cur = pc->next(0);
    if( cur != tail_ && cur->key_ != key){
      return std::make_pair(false, 0);
    }
  
    for(int i = level_; i >= 0; --i){
      if(prevs[i]->next(i) == cur){
        prevs[i]->setNext(i, cur->next(i));
        if(header_->next(i) == tail_){
          level_ --;
        }
      }
    }
    Node::dealloc(cur);
    count_ --;
    
    return std::make_pair(true, 0);
  }

private:
  void destroy(){
    while(header_->next(0) != tail_){
      Node * p = header_->next(0);
      header_->setNext(0, p->next(0));
      Node::dealloc(p);
    }
  }


private:
  int level_; // 0-based
  Node * header_;
  Node * tail_;
  int count_ ;
  static const int max_level_ = 6; // 0-based
};


TEST(SkipListTest, test){
  SkipList sl;
  {
    int key = 1, value = 2;
    ASSERT_EQ(std::make_pair(true, 0), sl.insert(key, value));
    ASSERT_EQ(std::make_pair(true, value), sl.get(key));
  }
  {
    int key = 2, value = 4;
    ASSERT_EQ(std::make_pair(true, 0), sl.insert(key, value));
    ASSERT_EQ(std::make_pair(true, value), sl.get(key));
  }
  {
    int key = 3, value = 4;
    ASSERT_EQ(std::make_pair(true, 0), sl.insert(key, value));
    ASSERT_EQ(std::make_pair(true, value), sl.get(key));
  }
  sl.print();

  sl.remove(1);
  sl.print("after remove(2)");
}

